Algorithms.11

平衡树

代码

二叉树的变种，区别在动态添加和删除叶节点，能够通过一些指标，对二叉树的形状变化进行监督，当发现树的形状开始变得不平衡的时候，立即修正二叉树的形状。

先看一张图

监督的重要指标 - 平衡因子，左子树的高度减去右子树的高度

平衡二叉树（AVL）：所有结点的平衡因子的绝对值都不超过1。即对平衡二叉树每个结点来说，其左子树的高度 - 右子树高度得到的差值只能为 1， 0 ， -1 这三个值。取得小于 -1或者大于1的值，都被视为打破了二叉树的平衡

当插入新节点打破平衡时，就需要一定的操作来维持平衡，即：左右旋

左旋

可以看见，节点‘2’的平衡因子目前为-2，所以需要选择右子树来维持平衡，首先断开右子树中最小成员‘3’，然后将2的右儿子作为新根节点，最后将‘3’查到‘2’的右节点上

def rotate_left(self):
    new_root = self.node.right.node
    new_sub_right = new_root.left.node
    old_root = self.node
    new_root.left.node = old_root
    old_root.right.node = new_sub_right
    self.node = new_root

右旋

def rotate_right(self):
    new_root = self.node.left.node
    new_sub_left = new_root.right.node
    old_root = self.node
    new_root.right.node = old_root
    old_root.left.node = new_sub_left
    self.node = new_root

根据平衡因子的情况，将失衡后的树分为四种情况

删除节点，按节点值大小找到对应节点后，找出右子树中最小节点，删除它后作为新根节点的右子树，将这个节点作为新的根节点，原根节点的左子树作为新节点的左子树

    def delete_node(self, value):
        if not self.node:
            return

        if value > self.node.value:
            self.node.right.delete_node(value)
        elif value < self.node.value:
            self.node.left.delete_node(value)
        else:
            if not self.node.left.node:
                self.node = self.node.right.node
            elif not self.node.right.node:
                self.node = self.node.left.node
            else:
                new_node = min_node(self.node.right.node)
                new_node.right.node = delete_min(self.node.right.node)
                new_node.left = self.node.left
                self.node = new_node

        self.update_heights()
        self.update_balances()